package org.example.leetcode.interview.backtrack;

import java.util.LinkedList;
import java.util.List;

public class LC0022 {
    List<String> ans = new LinkedList<>();
    StringBuilder sb = new StringBuilder();

    /**
     * 生成的括号包括, 作为打开的左半边括号以及作为关闭的右半边括号
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        backtracking(0, 0, n);
        return ans;
    }

    private void backtracking(int open, int close, int max) {
        if (sb.length() == max * 2) {
            ans.add(sb.toString());

            return;
        }

        if (open < max) {
            sb.append('(');
            backtracking(open + 1, close, max);
            sb.deleteCharAt(sb.length() - 1);
        }

        if (close < open) {
            sb.append(')');
            backtracking(open, close + 1, max);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}
